/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/permutation-index
   @Language: C++
   @Datetime: 16-02-09 05:14
   */

class Solution {
public:
	/**
	 * @param A: An array of integers
	 * @return: A long integer
	 * Tip:
	 * Cantor Expand
	 */
	long long permutationIndex(vector<int> &A) {
		// write your code here
		long long sum=0, fact=1, n=1;
		set<int> rights;
		for(int i=A.size(); i--;){
			rights.insert(A[i]);
			for(const auto &a:rights){
				if (a==A[i]) break;
				sum += fact;
			}
			fact *= n++;
		}
		return sum+1;
	}
};
